package string;


import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author justnow
 * Created on 2020-10-02
 * Description
 * <p>
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/javade-6chong-jie-fa-by-sdwwld/
 */
public class SwardOffer48_lengthOfLongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() <= 0) {
            return 0;
        }
        int length = s.length();
        int left = 0, max = 0;
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            //用i依次判断s中的每个字符，left表示与i构成的字符串中不包含重复的字符串。
            //如果当前包含i下标对应的字符，那么就需要通过left来判断重复的元素在哪里。
            //同时移除重复元素左边的元素和重复的内容，直到left为重复元素的下一个位置
            //如：abcdcefg
            //用i来索引每个元素，i从0到3时，不存在重复的元素，所以，每个元素都可以到集合中，每次插入到集合中，都判断一下集合的size最大值
            //当i为4时，c在set中存在，此时就需要将集合中abc都移除集合中，直到left下标为d为止。此时集合中的为dc

            while (left < length && set.contains(s.charAt(i))) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(i));
            max = Math.max(max, set.size());
        }
        return max;
    }

    /**
     * 方法二，用队列来实现
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        Queue<Character> queue = new LinkedList<>();
        int res = 0;
        for (char c : s.toCharArray()) {
            while (queue.contains(c)) { //保证插入的时候队列中的元素不重复
                queue.poll();
            }
            queue.add(c);
            res = Math.max(res, queue.size());
        }
        return res;
    }

    public static void main(String[] args) {
        int abcabcbb = lengthOfLongestSubstring("pwwkew");
        System.out.println(abcabcbb);
    }

}
